#include <stdio.h>
typedef struct Huffman
{
    int weigth; //权值
    int parent, lchild, rchild;
} Huffman, *PHuffman;
void Select(PHuffman T, int flag, int *index1, int *index2)
{
    int min = 1000;
    for (int i = 1; i <= flag; i++)
    {
        for (int j = 1; j < flag; j++)
        {

            if (T[i].parent == 0 && T[j].parent == 0 && i != j)
            {
                if (T[i].weigth + T[j].weigth < min)
                {
                    min = T[i].weigth + T[j].weigth;
                    *index1 = i;
                    *index2 = j;
                }
            }
        }
    }
    
}
void CreateHuffman(PHuffman T, int n) 
{
    if (n <= 1)
        return;
    int m = 2 * n - 1;           
    T = new Huffman[m + 1];      
    for (int i = 1; i <= m; i++) 
    {
        T[i].lchild = 0;
        T[i].rchild = T[i].lchild;
        T[i].parent = 0;
    }

    int weigth;
    printf("输入权值\n");
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &weigth);
        T[i].weigth = weigth;
    }
    for (int i = n + 1; i <= m; i++)
    {
        int s1, s2;
        Select(T, i - 1, &s1, &s2);
        T[s1].parent = i;
        T[s2].parent = i;
        T[i].lchild = s1;
        T[i].rchild = s2;
        T[i].weigth = T[s1].weigth + T[s2].weigth;
    }
    for (int i = 1; i <= m; i++)
    {
        printf("节点 %d 权值为 :%d 双亲为:%d 左孩子为 :%d 右孩子为:%d \n", i, T[i].weigth, T[i].parent, T[i].lchild, T[i].rchild);
    }
}
void test(int data[], int *x1, int *x2)
{
    int min = data[1] + data[2];
    int index1, index2;
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            if (data[i] + data[j] < min && i != j)
            {
                min = data[i] + data[j]; //重新为max赋值
                *x1 = i;
                *x2 = j; //重新为index1,index2 赋值
            }
        }
    }
}
int main(void)
{
    Huffman HT;
    int n = 6;
    CreateHuffman(&HT, n);

    return 0;
}
